As the demand for aggregate switching capacity increases, multiple-module switching systems are being adopted as a scalable alternative to a single-node output-buffered switch (see, for example, F. M. Chiussi, J. G. Kneuer, and Kumar V. P., “Low-cost scalable switching solutions for broadband networking: The ATLANTA architecture and chipset”, IEEE Communications Magazine, 35(12):44–53, December 1997.) At the same time, a significant amount of effort has been spent in designing complex scheduling algorithms which provide diversified Quality of Service (QoS) guarantees such as bounded delay, guaranteed bandwidth and fairness to individual flows or virtual connections. However, most of these techniques regulate access to a single contention point, and hence are directly applicable to output-buffered switches and multiplexors. Such a model does not adequately represent many of the evolved switch architectures, which employ multiple stages such as the ingress port, switch fabric and egress port and have contention points associated with each stage.
Feedback control through the mechanism of selective backpressure is well known in the context of multi-stage switches. However, the prior work in this field has concentrated primarily on increasing the throughput of the switching system. In one such instance such as that described by F. M. Chiussi, Y. Xia and V. P. Kumar in an article entitled “Backpressure In Shared-Memory Based ATM Switches Under Multiplexed Bursty Sources”, which apprered in Proc. IEEE INFOCOM' 96—Networking the Next Generation, Volume 2, pp 830–843, San Francisco, Calif., March 1996, whenever congestion occurs at an output link of the second stage, the first stage modules are pre-empted from sending traffic to that link by means of a per-output backpressure signal. Conceptually, it is possible to extend this idea by employing per-flow schedulers in each stage and using per-flow backpressure signals. However, such a replication of functionality in all the stages defeats the purpose of building multi-stage switches, not to mention the increased implementation complexity. Hence, we are motivated to build a system in which we relegate all the fine grain scheduling details to the slower (in terms of aggregate switching capacity) first stage, aggregate a set of flows into a single session in the second stage, and provide an intelligent feedback mechanism that enables to maintain the QoS guarantees at the per-flow level. Some of the recent work done by D. C. Stephens and H. Zhang and presented as a paper entitled “Implementing Distributed Packet Fair Queueing in a Scalable Switch Architecture”, which appeared in Proc. IEEE INFOCOM'98—Gateway to the 21st Century, Volume 1, pp. 282–290, San Francisco, Calif., March/April 1998, in multi-stage switches take a similar approach but do not address the issue of flow aggregation.
Employing queue length as an indication of congestion with asserting selective feedback with direct or indirect means is a well-known technique both in switching architectures and the Available Bit Rate (ABR) service. Use of the length of a fictitious, or virtual, queue instead of the length of an actual queue for that purpose has also been described before (See, for example, F. M. Chiussi, Y. Xia and V. P. Kumar, “Virtual Queueing Techniques for ABR Service: Improving ABR/VBR Interaction, Proc. IEEE INFOCOM'97—Driving the Information Revolution, Volume 1, pp 406–418, Kobe, Japan, April 1997. The latter method provides a reliable indication of congestion caused by a specific traffic component (ABR type traffic) in the presence of other traffic components (Variable Bit Rate, or VBR, type traffic) when each traffic component is allocated its separate queue and the ABR queue is given strictly lower priority than the VBR queue. The length of a virtual ABR queue is controlled using the reference static ABR service rate and the derived actual arrival rate.